The present invention relates to digital computer systems, and more particularly, to digital data compression schemes employed in digital computer systems.
Digital computer systems perform data compression to realize a more efficient use of finite storage space. The computer system typically includes a hardware component referred to as a compression accelerator, which accepts work requests or data requests from the host system to compress or decompress one or more blocks of the requested data. These compression accelerators often utilize a “DEFLATE” algorithm, which is a lossless compression scheme that combines the Lempel-Ziv (e.g., LZ77) compression algorithm, along with a Huffman algorithm to perform the compression. The computed output from the Huffman algorithm can be viewed as a variable-length code table for encoding a source symbol (such as a character in a file). The Huffman algorithm derives this table from the estimated probability or frequency of occurrence (weight) for each possible value of the source symbol.